package com.structure.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.TreeSet;
import java.util.stream.Collectors;

/**
 * @Author Tanyu
 * @Date 2020/6/11 16:19
 * @Description
 * @Version 1.0
 */
public class TheMedianOfOrdinalGroup {

  public static void main(String[] args) {
    Integer[] nums1={1,3,5,6,7};
    Integer[] nums2={1,2,4,6,8,9};

//    System.out.println(findMedianSortedArrays(nums1,nums2));
    System.out.println(findMedianSortedArrays1(nums1,nums2));
  }

  public static double findMedianSortedArrays(Integer[] A,Integer[] B){
    int m = A.length;
    int n = B.length;
    if (m > n) {
      return findMedianSortedArrays(B,A); // 保证 m <= n
    }
    int iMin = 0, iMax = m;
    while (iMin <= iMax) {
      int i = (iMin + iMax) / 2;
      int j = (m + n + 1) / 2 - i;
      if (j != 0 && i != m && B[j-1] > A[i]){ // i 需要增大
        iMin = i + 1;
      }
      else if (i != 0 && j != n && A[i-1] > B[j]) { // i 需要减小
        iMax = i - 1;
      }
      else { // 达到要求，并且将边界条件列出来单独考虑
        int maxLeft = 0;
        if (i == 0) { maxLeft = B[j-1]; }
        else if (j == 0) { maxLeft = A[i-1]; }
        else { maxLeft = Math.max(A[i-1], B[j-1]); }
        if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇数的话不需要考虑右半部分

        int minRight = 0;
        if (i == m) { minRight = B[j]; }
        else if (j == n) { minRight = A[i]; }
        else { minRight = Math.min(B[j], A[i]); }

        return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
      }
    }
    return 0.0;
  }

  public static double findMedianSortedArrays1(Integer[] A,Integer[] B){
    List<Integer> list = new ArrayList<>();
    list.addAll(Arrays.asList(A));
    list.addAll(Arrays.asList(B));
//    list.sort((a,b)->a-b);
    Collections.sort(list);
    if (list.size()%2==0){
      return (list.get(list.size()/2-1)+list.get(list.size()/2))/2;
    }else {
      return list.get(list.size()/2);
    }
  }

}
